/*
Esempio 1.
Problema di programmazione lineare 0-1.
Compito: 31 gennaio 2008.

Problema:
maximize
	13x1 + 16x2 + 25x3 + 35x4 
subject to 
	6x1 + 3x2 + 4x3	<= 12 
	9x2 + 4x3 + 8x4	<= 16 
	9x1 + 16x4	<= 22 
	x in {0,1}^4
	
Questo problema, portato in forma standard per GLPK, diventa:
maximize
	13x1 + 16x2 + 25x3 + 35x4 
subject to 
	p = 6x1 + 3x2 + 4x3			6 3 4 0
	q = 9x2 + 4x3 + 8x4			0 9 4 8
	r = 9x1 + 16x4				9 0 0 16
	x in {0,1}^4

bounds
	-inf <= p <= 12
	-inf <= q <= 16
	-inf <= r <= 22
	
	0 <= x1 <= 1
	0 <= x2 <= 1
	0 <= x3 <= 1
	0 <= x4 <= 1
	
*/

#include <stdio.h>
#include <stdlib.h>
#include "glpk.h"

int main(void) {

	/* Definizione delle strutture */
	glp_prob *lp;							// Handler del problema di PL
	int ia[1+1000], ja[1+1000];				// ia = array degli indici i (righe); ja = array degli indici j (colonne)
	double ar[1+1000], z, x1, x2, x3, x4;	// ar = array dei coefficienti, x1 a x3 = array delle variabili, z = funzione obiettivo
	
	// Creazione del problema in memoria e assegnazione di un nome mnemonico
	lp = glp_create_prob();
	glp_set_prob_name(lp, "Esempio1");
	
	// Tipologia del problema
	glp_set_obj_dir(lp, GLP_MAX);
	
	// Aggiunta delle righe del problema (tante quante sono i vincoli, si creano variabili ausiliarie che le identificano)
	glp_add_rows(lp, 3);
	
	// Inizializza righe
	glp_set_row_name(lp, 1, "p");
	glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 12.0);	// p
	
	glp_set_row_name(lp, 2, "q");
	glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 16.0);	// q
	
	glp_set_row_name(lp, 3, "r");
	glp_set_row_bnds(lp, 3, GLP_UP, 0.0, 22.0);	// r
	
	// Aggiunta delle colonne del problema (tante quante sono le variabili)
	glp_add_cols(lp, 4);
	
	// Inizializza colonne (con coefficienti della funzione obiettivo)
	glp_set_col_name(lp, 1, "x1");
	glp_set_col_bnds(lp, 1, GLP_DB, 0.0, 1.0);	// x1
	glp_set_obj_coef(lp, 1, 13.0);
	
	glp_set_col_name(lp, 2, "x2");
	glp_set_col_bnds(lp, 2, GLP_DB, 0.0, 1.0);	// x2
	glp_set_obj_coef(lp, 2, 16.0);

	glp_set_col_name(lp, 3, "x3");
	glp_set_col_bnds(lp, 3, GLP_DB, 0.0, 1.0);	// x3
	glp_set_obj_coef(lp, 4, 25.0);
	
	glp_set_col_name(lp, 4, "x4");
	glp_set_col_bnds(lp, 4, GLP_DB, 0.0, 1.0);	// x4
	glp_set_obj_coef(lp, 4, 35.0);
	
	// Inizializza la matrice 
	//	6 3 4 0
	//	0 9 4 8
	//	9 0 0 16
	ia[1] = 1, ja[1] = 1, ar[1] = 6.0;
	ia[2] = 1, ja[2] = 2, ar[2] = 3.0;
	ia[3] = 1, ja[3] = 3, ar[3] = 4.0;
	ia[4] = 1, ja[4] = 4, ar[4] = 0.0; // prima riga -> 6x1 + 3x2 + 4x3
	
	ia[5] = 2, ja[5] = 1, ar[5] = 0.0;
	ia[6] = 2, ja[6] = 2, ar[6] = 9.0;
	ia[7] = 2, ja[7] = 3, ar[7] = 4.0;
	ia[8] = 2, ja[8] = 4, ar[8] = 8.0; // seconda riga -> 9x2 + 4x3 + 8x4
	
	ia[9] = 3, ja[9] = 1, ar[9] = 9.0;
	ia[10] = 3, ja[10] = 2, ar[10] = 0.0;
	ia[11] = 3, ja[11] = 3, ar[11] = 0.0;
	ia[12] = 3, ja[12] = 4, ar[12] = 16.0; // terza riga -> 9x1 + 16x4
	
	// Caricamento della matrice
	glp_load_matrix(lp, 8, ia, ja, ar);
	
	// Soluzione
	glp_simplex(lp, NULL);
	
	// Assegnazione dei valori alle variabili (per mostrare la soluzione)
	z = glp_get_obj_val(lp);
	x1 = glp_get_col_prim(lp, 1);
	x2 = glp_get_col_prim(lp, 2);
	x3 = glp_get_col_prim(lp, 3);
	x4 = glp_get_col_prim(lp, 4);
	
	// Stampa su stdout del risultato
	printf("\nObjective\nz = %g;\nx1 = %g, x2 = %g, x3 = %g, x4 = %g.\n", z, x1, x2, x3, x4);
	glp_delete_prob(lp);
	
	return 0;
	
}
